数据结构(C语言) —— 堆栈

堆栈的基本概念

堆栈是一种特殊的线性表，其数据元素以及数据元素间的逻辑关系和线性表的完全相同，其差别是：线性表允许在任意位置插入和删除数据元素，而堆栈只允许在固定一端进行插入和删除数据元素操作。
堆栈中允许进行插入和删除操作的一端成为栈顶，另一端成为栈底；最后进入堆栈的数据元素总是最先退出堆栈，因此堆栈也称作后进先出的线性表。

堆栈的顺序表示和实现（顺序堆栈）

1.顺序堆栈的存储结构

定义结构体如下：

typedef struct
{
    DataType stack[MaxStackSize];
    int top;
} SeqStack;

2.顺序堆栈的操作实现

1.初始化

void StackInitiate(SeqStack *S)
{
    S->top = 0;            //初始化栈顶下标值（相当于数据元素个数）
}

2.判断非空否

int StackNotEmpty(SeqStack S)
//非空返回1，空返回0。
{
    if(S.top <= 0)return 0;
    else return 1;
}

3.入栈

int StackPush(SeqStack *S, DataType x)
//把数据元素值x存入顺序堆栈S中，成功返回1，失败返回0。
{
    if(S->top >= MaxStackSize)
    {
        printf("堆栈已满，无法入栈！");
        return 0;
    }
    else
    {
        S->stack[S->top] = x;
        S->top ++;
        return 1;
    }
}

4.出栈

int StackPop(SeqStack *S, DataType *d)
//取出的栈顶数据元素值由参数d带回，成功返回1，失败返回0。
{
    if(S->top <= 0)
    {
        printf("堆栈已空！");
        return 0;
    }
    else
    {
        S->top --;
        *d = S->stack[S->top];
        return 1;
    }
}

5.取栈顶数据元素

int StackTop(SeqStack S, DataType *d)
{
    if(S.top <= 0)
    {
        printf("堆栈已空！");
        return 0;
    }
    else
    {
        *d = S.stack[S.top -1];
        return 1;
    }
}

堆栈的链式表示和实现（链式堆栈）

1.链式堆栈的存储结构

结点结构体定义如下：

typedef struct snode
{
    DataType data;
    struct snode *next;
} LSNode;

2.链式堆栈的操作实现

1.初始化

void StackInitiate(LSNode **head)
//初始化带头结点链式堆栈
{
    *head = (LSNode *)malloc(sizeof(LSNode));
    (*head)->next = NULL;
}

2.判断非空否

int StackNotEmpty(LSNode *head)
{
    if(head->next == NULL)return 0;
    else return 1;
}

3.入栈

void StackPush(LSNode *head, DataType x)
{
    LSNode *p;

    p = (LSNode *)malloc(sizeof(LSNode));
    p->data = x;
    p->next = head->next;
    head->next = p;
}

4.出栈

int StackPop(LSNode *head, DataType *d)
{
    LSNode *p = head->next;
    if(p == NULL)
    {
        printf("堆栈已空！");
        return 0;
    }

    head->next = p->next;
    *d = p->data;
    free(p);
    return 1;
}

5.取栈顶数据元素

int StackTop(LSNode *head, DataType *d)
{
    LSNode *p = head->next;
    if(p == NULL)
    {
        printf("堆栈已空!");
        return 0;
    }

    *d = p->data;
    return 1;
}

6.撤销动态申请空间

void Destory(LSNode *head)
{
    LSNode *p, *p1;

    p = head;
    while(p!=NULL)
    {
        p1 = p;
        p = p->next;
        free(p1);
    }
}